from typing import List

class Solution:

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(index):
            if index == len(nums):
                result.append(temp[:])  # Append a copy of temp
                return
            for i in range(len(nums)):
                # If the number is already used or (it's the same as previous and previous is not used)
                if flags[i] or (i > 0 and nums[i] == nums[i - 1] and not flags[i - 1]):
                    continue
                flags[i] = True
                temp.append(nums[i])
                dfs(index + 1)
                temp.pop()  # Backtrack by removing the last number
                flags[i] = False

        nums.sort()  # Sort the numbers to handle duplicates
        result = []
        temp = []
        flags = [False] * len(nums)
        dfs(0)
        return result

# Example usage:
sol = Solution()
print(sol.permuteUnique([1, 1, 2]))
print(sol.permuteUnique([1, 2, 3]))
